package J2_6;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class test {
        private class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;

            TreeNode() {
            }

            TreeNode(int val) {
                this.val = val;
            }

            TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
     //二叉树前序非递归遍历实现 。
     public List<Integer> preorderTraversal1(TreeNode root) {
            List<Integer> list = new LinkedList<>();
            if(root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || !stack.empty()) {
                while (root != null) {
                    list.add(root.val);
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop().right;
            }
            return list;
     }
    public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new LinkedList<>();
            if (root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()) {
                TreeNode cur = stack.pop();
                list.add(cur.val);
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
            return list;

    }


}
